1. Field of the Invention
The present invention relates to a divider for carrying out division using a semiconductor integrated circuit, and particularly to a divider capable of fast division.
2. Description of Related Art
Recently, computer graphics techniques have been flourishing with the increase in the performance of computers. Since the computer graphics requires enormous amount of numerical computation, extremely fast numerical processing is needed to implement it. In particular, since the computer graphics carries out division much more frequently than ordinary numerical processing, it requires much faster division by hardware instead of software which is usually employed to carry out division in a comparatively large amount of time.
FIG. 19 is a block diagram showing a conventional divider implemented by hardware, which is disclosed in JP-A 1-321517 (1989). In this figure, the reference numeral 123 designates a memory such as a ROM, 125, 126, 127 and 128 designate first, second, third and fourth data bus selectors (MUX), 133 and 134 designate first and second multipliers, 137 designates a two's complementer, and 139 designates an adder.
Its operation will be described. The divider obtains the quotient b.sub.i /a.sub.i by sequentially multiplying both the dividend b.sub.i and the divisor a.sub.i by the same values such that the product of the divisor a.sub.i and these values converge to one. This method is called multiply convergence division, or reciprocal approximate division.
The memory 123 inputs a divisor 1 (a.sub.i) as an address input, and outputs an approximate value of a reciprocal of the divisor 1. The first data bus selector 125 inputs the output 124 of the memory 123 and the output 138 of the two's complementer 137; the second data bus selector 126 inputs the divisor, the output 135 of the first multiplier 133 and the output 136 of the second multiplier 134; the third data bus selector 127 inputs the output 124 of the memory 123 and the output 138 of the two's complementer 137; and the fourth data bus selector 128 inputs the dividend, and the output 136 of the second multiplier 134. The first multiplier 133 inputs the output 129 of the first data bus selector 125 as a first input, and the output 130 of the second data bus selector 126 as a second input, and supplies their product to the second data bus selector 126, the two's complementer 137 and the adder 139. The second multiplier 134 inputs the output 131 of the third data bus selector 127 as a first input, and the output 132 of the fourth data bus selector 128 as a second input, and supplies their product to the second data bus selector 126, the fourth data bus selector 128, and the adder 139. The adder 139 outputs the sum of the outputs of the first and second multipliers 133 and 134 as the quotient.
The conventional divider with such an arrangement has the following problems.
1. The first and second multipliers each have an m.times.m/2 bit structure each, and carry out the multiplication of that scale for each loop of the computation, resulting in rather large delay times. Usually, the multiplier forms a plurality of partial products from a multiplier and a multiplicand, adds the partial products by adders such as carry save adders until the partial products are reduced to two, and finally adds the two partial products by an adder like a ripple carry adder, thereby completing the multiplication. To improve the speed of the multiplication, various ideas are proposed such as reduction in the number of partial products by using the Booth algorithm, fast summing up of the partial products by the Wallace tree, and fast final addition by a carry lookahead adder.
The delay times of the first and second multipliers, however, are still large even if these methods are used. Accordingly, it is unavoidable that the conventional divider takes a substantial delay time proportional to the number of multiplications. In other words, it takes a long division time due to the delay of the multipliers when using the conventional divider including the common multipliers.
2. The division time further increases owing to the two's complementer which is passed through for each computing loop. This is because the two's complementer includes a kind of an adder, and the delay time due to the adder is added to the delay of the multipliers. In addition, the two's complementer increases the amount of hardware.
3. Since the entire circuit is occupied throughout a division operation, the next computation cannot be started until that division has been completed. This makes it impossible to adopt the pipeline processing to increase the speed.